package Competiton;

import java.util.*;

public class CompetitionOf251 {

    public static void main(String[] args) {
        System.out.println(SolutionOfrearrangeSticks.rearrangeSticks(20, 11));
    }

    static class SolutionOfsubsetXORSum {
        public static int subsetXORSum(int[] nums) {
            int len = nums.length, res = 0;
            if (len == 0)
                return res;
            List<ArrayList<Integer>> arrays = getSubArrays(nums);
            for (int i = 0; i < arrays.size(); i++) {
                ArrayList<Integer> sub = arrays.get(i);
                int temp = 0;
                for (int j = 0; j < sub.size(); j++) {
                    temp ^= sub.get(j);
                }
                res += temp;
            }
            return res;
        }

        public static List<ArrayList<Integer>> getSubArrays(int[] nums) {
            int count = (int) Math.pow(2, nums.length);
            List<ArrayList<Integer>> arrays = new ArrayList<ArrayList<Integer>>();
            for (int i = 1; i < count; i++) {
                List<Integer> subarray = new ArrayList<Integer>();
                int temp = i;
                int index = 0;
                while (temp != 0) {
                    if ((temp & 1) == 1) {
                        subarray.add(nums[index]);
                    }
                    index++;
                    temp = temp >> 1;
                }
                arrays.add((ArrayList<Integer>) subarray);
            }
            return arrays;
        }
    }

    static class SolutionOfminSwaps {
        // 0 1 个数相差不能大于1，相等时首位为0或1都行，相差一个时谁多谁放在前面
        // 找应该是0的地方但是为1的情形则要交换一次
        public static int minSwaps(String s) {
            char[] ch = s.toCharArray();
            int count0 = 0, count1 = 0, swaps = 0;
            for (char c : ch) {
                if (c == '0')
                    ++count0;
                else
                    ++count1;
            }
            if (Math.abs(count0 - count1) > 1)
                return -1;
            else if (count0 > count1) {
                swaps = countSwaps(ch, 0);
            } else if (count0 < count1) {
                swaps = countSwaps(ch, 1);
            } else {
                if (ch[0] == '0')
                    swaps = countSwaps(ch, 0);
                else
                    swaps = countSwaps(ch, 1);
            }
            return swaps;
        }

        public static int countSwaps(char[] ch, int start) {
            int count = 0;
            for (int i = start; i < ch.length; i += 2) {
                if (ch[i] == '1')
                    ++count;
            }
            return count;
        }
    }

    static class SolutionOfrearrangeSticks {
        static int mod = (int) 1e9 + 7;

        public static int rearrangeSticks(int n, int k) {
            int[] nums = new int[n];
            for (int i = 0; i < n; ++i)
                nums[i] = i + 1;
            int res = 0;
            pai(0, nums, res, k);
            return res;
        }

        public static void pai(int index, int[] a, int res, int outk) {
            if (index == a.length) {
                int temp = 0, count = 0;
                for (int j = 0; j < a.length; j++) {
                    if (a[j] > temp) {
                        temp = a[j];
                        ++count;
                    }
                }
                if (count == outk)
                    res = (res + 1) % mod;
                return;
            }
            for (int k = index; k < a.length; k++) {
                {// 交换两个元素的位置
                    int te = a[index];
                    a[index] = a[k];
                    a[k] = te;
                }
                // 这儿一定是index+1,而不是k+1;
                // 递归发现更多的排列
                pai(index + 1, a, res, outk);

                {// 递归之后需要回溯
                    int te = a[index];
                    a[index] = a[k];
                    a[k] = te;
                }
            }
        }
    }
}
